#!/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：V2 
@File    ：T1.py
@IDE     ：PyCharm 
@Author  ：郭星
@Date    ：2025/10/23 16:00 
'''
# !/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：V2 
@File    ：algorithm_comparison.py
@IDE     ：PyCharm 
@Author  ：郭星
@Date    ：2025/10/18 0:01 
'''
# !/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
四种调度算法对比（含改进禁忌搜索：新增优劣种群分离策略）
'''

import os
import json
import random
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import time
from datetime import datetime
from typing import List, Tuple, Dict, Optional


# 统一随机种子，便于复现实验

def set_seed(seed: int = 42):
    random.seed(seed)
    np.random.seed(seed)


# 设置中文显示（尽量兼容无 SimHei 的环境）
try:
    plt.rcParams["font.family"] = ["SimHei", "SimHei", "SimHei"]
except Exception:
    pass
plt.rcParams["axes.unicode_minus"] = False


class GasSchedulingInstanceGenerator:
    """气体调度算例生成器与加载器"""

    @staticmethod
    def load_instance(file_path: str) -> Dict:
        if not os.path.exists(file_path):
            raise FileNotFoundError(f"算例文件不存在: {file_path}")

        with open(file_path, 'r', encoding='utf-8') as f:
            instance = json.load(f)

        # 验证必要字段
        required_keys = ['problem_type', 'parameters', 'processing_times']
        for key in required_keys:
            if key not in instance:
                raise ValueError(f"算例格式错误，缺少必要字段: {key}")

        # 兼容旧算例（充气时间二维化）
        if len(np.array(instance['processing_times']['inflation_time']).shape) == 1:
            num_workpieces = instance['parameters']['num_workpieces']
            num_components = instance['parameters']['num_components']
            old_inflation = np.array(instance['processing_times']['inflation_time'])
            new_inflation = np.tile(old_inflation[:, np.newaxis], (1, num_components))
            instance['processing_times']['inflation_time'] = new_inflation.tolist()
            print(f"警告：旧算例已自动转换为多组分充装格式")

        # 补充缺失参数
        if 'num_clean_eq' not in instance['parameters']:
            instance['parameters']['num_clean_eq'] = 1
        if 'num_shake_eq' not in instance['parameters']:
            instance['parameters']['num_shake_eq'] = 1
        if 'clean_time' not in instance['processing_times']:
            instance['processing_times']['clean_time'] = 5
        if 'shake_unit_time' not in instance['processing_times']:
            instance['processing_times']['shake_unit_time'] = 2

        return instance

    @staticmethod
    def list_instances(directory: str = ".") -> List[str]:
        instance_files = []
        for root, _, files in os.walk(directory):
            for file in files:
                if file.endswith(".json"):
                    try:
                        with open(os.path.join(root, file), 'r') as f:
                            data = json.load(f)
                            if data.get('problem_type') == 'gas_scheduling':
                                instance_files.append(os.path.join(root, file))
                    except:
                        continue
        return sorted(instance_files)


class BaseSchedulingAlgorithm:
    """调度算法基类"""

    def __init__(self,
                 instance: Dict,
                 max_iter: int = 100,
                 name: str = "算法"):
        params = instance['parameters']
        processing_times = instance['processing_times']

        # 基础参数
        self.num_workpieces = params['num_workpieces']
        self.num_components = params['num_components']
        self.num_inflation_eq = params['num_inflation_eq']
        self.num_analysis_eq_per_component = params['num_analysis_eq_per_component']
        self.num_clean_eq = params['num_clean_eq']
        self.num_shake_eq = params['num_shake_eq']

        # 加工时间
        self.inflation_time = np.array(processing_times['inflation_time'])
        self.analysis_time = np.array(processing_times['analysis_time'])
        self.clean_time = processing_times['clean_time']
        self.shake_unit_time = processing_times['shake_unit_time']
        self.shake_time = np.array([self.num_components * self.shake_unit_time
                                    for _ in range(self.num_workpieces)])

        self.max_iter = max_iter
        self.name = name
        self.best_solution = None
        self.best_time = float('inf')
        self.iteration_best_times = []
        self.execution_time = 0
        # 运行时缓存（避免重复计算同一解的工期）
        self._time_cache = {}

    def time_of(self, solution: Dict) -> float:
        """带缓存地计算解的完成时间"""
        try:
            h = self.solution_hash(solution)  # 优先用显式哈希（TS/GA一致）
        except Exception:
            h = id(solution)
        if h not in self._time_cache:
            self._time_cache[h] = self.calculate_completion_time(solution)
        return self._time_cache[h]

    def initialize_solution(self) -> Dict:
        """初始化解（多组分充装适配）"""
        # 1. 清洗阶段
        clean_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        clean_eq = [random.randint(0, self.num_clean_eq - 1)
                    for _ in range(self.num_workpieces)]

        # 2. 充装阶段（保证每瓶底气在该瓶最后充）
        # 约定：最后一个组分为底气（如 N₂）。若你的数据不是该约定，请按需修改 bottom_comp 的取值。
        bottom_comp = self.num_components - 1
        # 为每个工件构造“非底气随机顺序 + 底气最后”的子序列
        per_wp_sequences = []
        for wp in range(self.num_workpieces):
            non_bottom = [(wp, c) for c in range(self.num_components) if c != bottom_comp]
            random.shuffle(non_bottom)
            per_wp_sequences.append(non_bottom + [(wp, bottom_comp)])
        # 交错合并（保持每瓶内部顺序的同时，随机全局交织）
        inflation_order = []
        cursors = [0] * self.num_workpieces
        remaining = sum(len(seq) for seq in per_wp_sequences)
        while remaining > 0:
            i = random.randrange(self.num_workpieces)
            if cursors[i] < len(per_wp_sequences[i]):
                inflation_order.append(per_wp_sequences[i][cursors[i]])
                cursors[i] += 1
                remaining -= 1

        inflation_eq = [
            [random.randint(0, self.num_inflation_eq - 1)
             for _ in range(self.num_components)]
            for _ in range(self.num_workpieces)
        ]

        inflation_eq = [
            [random.randint(0, self.num_inflation_eq - 1)
             for _ in range(self.num_components)]
            for _ in range(self.num_workpieces)
        ]

        # 3. 摇匀阶段
        shake_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        shake_eq = [random.randint(0, self.num_shake_eq - 1)
                    for _ in range(self.num_workpieces)]

        # 4. 分析阶段
        analysis_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        component_groups = []
        group_test_order = []
        analysis_eq = []
        for _ in range(self.num_workpieces):
            max_groups = random.randint(1, self.num_components)
            groups = [random.randint(0, max_groups - 1) for _ in range(self.num_components)]
            component_groups.append(groups)
            unique_groups = list(sorted(set(groups)))
            random.shuffle(unique_groups)
            group_test_order.append(unique_groups)
            eq_for_workpiece = []
            for group_id in unique_groups:
                components_in_group = [j for j, g in enumerate(groups) if g == group_id]
                eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1)
                                for _ in components_in_group]
                eq_for_workpiece.append(eq_for_group)
            analysis_eq.append(eq_for_workpiece)

        return {
            'clean_order': clean_order,
            'clean_eq': clean_eq,
            'inflation_order': inflation_order,
            'inflation_eq': inflation_eq,
            'shake_order': shake_order,
            'shake_eq': shake_eq,
            'analysis_order': analysis_order,
            'component_groups': component_groups,
            'group_test_order': group_test_order,
            'analysis_eq': analysis_eq
        }

    def calculate_completion_time(self, solution: Dict) -> float:
        """计算四阶段总时间"""
        # 1. 清洗阶段
        clean_machine_time = [0] * self.num_clean_eq
        workpiece_clean_end = {}
        for workpiece in solution['clean_order']:
            eq = solution['clean_eq'][workpiece]
            start_time = clean_machine_time[eq]
            end_time = start_time + self.clean_time
            clean_machine_time[eq] = end_time
            workpiece_clean_end[workpiece] = end_time
        clean_completion_time = max(clean_machine_time)

        # 2. 充装阶段
        inflation_machine_time = [0] * self.num_inflation_eq
        workpiece_comp_inflate_end = {
            wp: {comp: 0 for comp in range(self.num_components)}
            for wp in range(self.num_workpieces)
        }
        for (wp, comp) in solution['inflation_order']:
            eq = solution['inflation_eq'][wp][comp]
            start_time = max(
                inflation_machine_time[eq],
                workpiece_clean_end.get(wp, 0),
                max(workpiece_comp_inflate_end[wp].values())
            )
            end_time = start_time + self.inflation_time[wp][comp]
            inflation_machine_time[eq] = end_time
            workpiece_comp_inflate_end[wp][comp] = end_time
        inflation_completion_time = max(inflation_machine_time)
        workpiece_inflate_end = {
            wp: max(workpiece_comp_inflate_end[wp].values())
            for wp in range(self.num_workpieces)
        }

        # 3. 摇匀阶段
        shake_machine_time = [0] * self.num_shake_eq
        workpiece_shake_end = {}
        for workpiece in solution['shake_order']:
            eq = solution['shake_eq'][workpiece]
            start_time = max(shake_machine_time[eq], workpiece_inflate_end.get(workpiece, 0))
            end_time = start_time + self.shake_time[workpiece]
            shake_machine_time[eq] = end_time
            workpiece_shake_end[workpiece] = end_time
        shake_completion_time = max(shake_machine_time)

        # 4. 分析阶段
        analysis_machine_time = [[0 for _ in range(self.num_analysis_eq_per_component)]
                                 for _ in range(self.num_components)]
        for workpiece in solution['analysis_order']:
            if workpiece < 0 or workpiece >= self.num_workpieces:
                continue
            start_analysis_time = workpiece_shake_end.get(workpiece, 0)
            group_test_order = solution['group_test_order'][workpiece]
            analysis_eq = solution['analysis_eq'][workpiece]

            for group_idx, group_id in enumerate(group_test_order):
                if group_idx < 0 or group_idx >= len(analysis_eq):
                    continue
                components_in_group = [j for j, g in enumerate(solution['component_groups'][workpiece])
                                       if g == group_id]
                eq_for_group = analysis_eq[group_idx]
                if len(eq_for_group) != len(components_in_group):
                    eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1)
                                    for _ in components_in_group]
                    analysis_eq[group_idx] = eq_for_group

                group_ready_time = start_analysis_time
                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    group_ready_time = max(group_ready_time, analysis_machine_time[component][eq])

                max_analysis_time = max(
                    self.analysis_time[workpiece][component]
                    for comp_idx, component in enumerate(components_in_group)
                    if comp_idx < len(eq_for_group)
                ) if components_in_group else 0
                group_end_time = group_ready_time + max_analysis_time

                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    analysis_machine_time[component][eq] = group_end_time
                start_analysis_time = group_end_time

        analysis_completion_time = max(max(machine_times) for machine_times in analysis_machine_time)

        return max(clean_completion_time, inflation_completion_time,
                   shake_completion_time, analysis_completion_time)

    def get_schedule_details(self, solution: Dict) -> Tuple[Dict, Dict, Dict, Dict, float]:
        """返回四阶段调度详情及分析阶段偏移量"""
        # 1. 清洗阶段
        clean_details = {eq: [] for eq in range(self.num_clean_eq)}
        clean_machine_time = [0] * self.num_clean_eq
        workpiece_clean_end = {}
        for workpiece in solution['clean_order']:
            eq = solution['clean_eq'][workpiece]
            start = clean_machine_time[eq]
            end = start + self.clean_time
            clean_machine_time[eq] = end
            workpiece_clean_end[workpiece] = end
            clean_details[eq].append({'workpiece': workpiece, 'start': start, 'end': end})

        # 2. 充装阶段
        inflation_details = {eq: [] for eq in range(self.num_inflation_eq)}
        inflation_machine_time = [0] * self.num_inflation_eq
        workpiece_comp_inflate_end = {
            wp: {comp: 0 for comp in range(self.num_components)}
            for wp in range(self.num_workpieces)
        }
        for (wp, comp) in solution['inflation_order']:
            eq = solution['inflation_eq'][wp][comp]
            start = max(
                inflation_machine_time[eq],
                workpiece_clean_end.get(wp, 0),
                max(workpiece_comp_inflate_end[wp].values())
            )
            end = start + self.inflation_time[wp][comp]
            inflation_machine_time[eq] = end
            workpiece_comp_inflate_end[wp][comp] = end
            inflation_details[eq].append({
                'workpiece': wp, 'component': comp, 'start': start, 'end': end,
                'duration': self.inflation_time[wp][comp]
            })
        workpiece_inflate_end = {
            wp: max(workpiece_comp_inflate_end[wp].values())
            for wp in range(self.num_workpieces)
        }

        # 3. 摇匀阶段
        shake_details = {eq: [] for eq in range(self.num_shake_eq)}
        shake_machine_time = [0] * self.num_shake_eq
        workpiece_shake_end = {}
        for workpiece in solution['shake_order']:
            eq = solution['shake_eq'][workpiece]
            start = max(shake_machine_time[eq], workpiece_inflate_end.get(workpiece, 0))
            end = start + self.shake_time[workpiece]
            shake_machine_time[eq] = end
            workpiece_shake_end[workpiece] = end
            shake_details[eq].append({
                'workpiece': workpiece, 'start': start, 'end': end,
                'group_count': self.num_components
            })

        # 4. 分析阶段
        analysis_details = {c: {eq: [] for eq in range(self.num_analysis_eq_per_component)}
                            for c in range(self.num_components)}
        analysis_machine_time = [[0] * self.num_analysis_eq_per_component for _ in range(self.num_components)]
        all_analysis_starts = []

        for workpiece in solution['analysis_order']:
            if workpiece < 0 or workpiece >= self.num_workpieces:
                continue
            start_analysis_time = workpiece_shake_end.get(workpiece, 0)
            group_test_order = solution['group_test_order'][workpiece]
            analysis_eq = solution['analysis_eq'][workpiece]

            for group_idx, group_id in enumerate(group_test_order):
                if group_idx < 0 or group_idx >= len(analysis_eq):
                    continue
                components_in_group = [j for j, g in enumerate(solution['component_groups'][workpiece]) if
                                       g == group_id]
                eq_for_group = analysis_eq[group_idx]
                if len(eq_for_group) != len(components_in_group):
                    eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in
                                    components_in_group]

                group_ready_time = start_analysis_time
                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    group_ready_time = max(group_ready_time, analysis_machine_time[component][eq])

                all_analysis_starts.append(group_ready_time)

                max_analysis_time = max(
                    self.analysis_time[workpiece][component]
                    for comp_idx, component in enumerate(components_in_group)
                    if comp_idx < len(eq_for_group)
                ) if components_in_group else 0
                group_end_time = group_ready_time + max_analysis_time

                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    analysis_machine_time[component][eq] = group_end_time
                    analysis_details[component][eq].append({
                        'workpiece': workpiece, 'start': group_ready_time, 'end': group_end_time,
                        'group': group_id, 'individual_time': self.analysis_time[workpiece][component]
                    })
                start_analysis_time = group_end_time

        analysis_start_offset = min(all_analysis_starts) if all_analysis_starts else 0
        return clean_details, inflation_details, shake_details, analysis_details, analysis_start_offset

    def plot_gantt_chart(self, solution: Dict = None, title_suffix: str = ""):
        """绘制甘特图"""
        if solution is None:
            solution = self.best_solution
        if solution is None:
            print(f"{self.name} 没有可用的调度方案进行绘制")
            return

        clean_details, inflation_details, shake_details, analysis_details, analysis_start_offset = self.get_schedule_details(
            solution)
        total_global_time = self.time_of(solution)

        # 颜色分配
        base_colors = plt.cm.tab10(np.linspace(0, 1, min(10, self.num_workpieces)))
        wp_comp_colors = {}
        for wp in range(self.num_workpieces):
            base_color = base_colors[wp % 10]
            for comp in range(self.num_components):
                lightness = 0.8 + (comp % 3) * 0.15
                wp_comp_colors[(wp, comp)] = (
                    min(base_color[0] * lightness, 1.0),
                    min(base_color[1] * lightness, 1.0),
                    min(base_color[2] * lightness, 1.0)
                )

        # 创建子图
        top_fig_height = (self.num_clean_eq + self.num_inflation_eq + self.num_shake_eq) * 0.8 + 2
        analysis_eq_total = self.num_components * self.num_analysis_eq_per_component
        bottom_fig_height = analysis_eq_total * 0.6 + 1
        fig, (ax_top, ax_bottom) = plt.subplots(
            2, 1, figsize=(16, top_fig_height + bottom_fig_height + 1),
            gridspec_kw={'height_ratios': [top_fig_height, bottom_fig_height]}
        )
        fig.suptitle(f'{self.name} 气体调度甘特图 {title_suffix}', fontsize=16, y=0.98)

        # 上方子图：清洗+充装+摇匀（全局时间）
        y_base = 0
        stage_y_ranges = {}

        # 清洗阶段
        stage_name = "清洗阶段"
        stage_eq_count = self.num_clean_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(clean_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_global_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in clean_details[eq]:
                wp = task['workpiece']
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=base_colors[wp % 10], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{wp}', ha='center', va='center',
                    color='white', fontweight='bold', fontsize=8
                )

        y_base = stage_y_end + 0.5

        # 充装阶段
        stage_name = "充装阶段（多组分）"
        stage_eq_count = self.num_inflation_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(inflation_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_global_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in inflation_details[eq]:
                wp = task['workpiece']
                comp = task['component']
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=wp_comp_colors[(wp, comp)], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{wp}-组{comp}', ha='center', va='center',
                    color='white', fontweight='bold', fontsize=7
                )

        y_base = stage_y_end + 0.5

        # 摇匀阶段
        stage_name = "摇匀阶段"
        stage_eq_count = self.num_shake_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(shake_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_global_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in shake_details[eq]:
                wp = task['workpiece']
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=base_colors[wp % 10], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{wp}\n({task["group_count"]}组分)',
                    ha='center', va='center', color='white', fontweight='bold', fontsize=7
                )

        # 上方子图样式
        ax_top.set_xlim(-total_global_time * 0.05, total_global_time * 1.1)
        ax_top.set_ylim(0, stage_y_end + 1)
        ax_top.set_yticks([])
        ax_top.set_xlabel('全局时间', fontsize=11)
        ax_top.set_title('上方：清洗 → 充装（多组分） → 摇匀 阶段（全局时间）', fontsize=12, pad=10)
        ax_top.grid(True, axis='x', linestyle='--', alpha=0.7)

        # 阶段分隔线
        for stage_name, (y_start, y_end) in stage_y_ranges.items():
            ax_top.axhline(y=y_start - 0.3, xmin=0, xmax=1, color='red', linestyle='--', alpha=0.7)
            ax_top.text(total_global_time * 0.5, y_start - 0.6, f'【{stage_name}】',
                        ha='center', va='center', fontweight='bold', color='red', fontsize=10)

        # 下方子图：分析阶段（相对时间）
        y_pos_current = 1
        y_ticks = []
        y_tick_labels = []
        all_groups = {}
        max_relative_end = 0

        for component in sorted(analysis_details.keys()):
            for eq in sorted(analysis_details[component].keys()):
                y_ticks.append(y_pos_current)
                y_tick_label = f'组分{component} 分析设备{eq}'
                y_tick_labels.append(y_tick_label)

                for task in analysis_details[component][eq]:
                    wp = task['workpiece']
                    comp = component
                    relative_start = task['start'] - analysis_start_offset
                    relative_end = task['end'] - analysis_start_offset
                    max_relative_end = max(max_relative_end, relative_end)

                    group_key = (wp, task['group'])
                    if group_key not in all_groups:
                        all_groups[group_key] = []
                    all_groups[group_key].append((y_pos_current, relative_start, relative_end))

                    ax_bottom.barh(
                        y_pos_current, relative_end - relative_start, left=relative_start, height=0.6,
                        color=wp_comp_colors[(wp, comp)], edgecolor='black', alpha=0.9
                    )
                    ax_bottom.text(
                        relative_start + (relative_end - relative_start) / 2, y_pos_current,
                        f'瓶{wp}-组{comp}\n({task["individual_time"]}s)',
                        ha='center', va='center', color='white', fontweight='bold', fontsize=7
                    )

                y_pos_current += 1
            y_pos_current += 0.5

        # 串联组连接线
        for (wp, group_id), tasks in all_groups.items():
            if len(tasks) > 1:
                mid_time = (tasks[0][1] + tasks[0][2]) / 2
                y_min = min([t[0] for t in tasks]) - 0.3
                y_max = max([t[0] for t in tasks]) + 0.3
                ax_bottom.plot(
                    [mid_time, mid_time], [y_min, y_max],
                    'k--', linewidth=1.5, alpha=0.7
                )
                ax_bottom.text(
                    mid_time, y_max + 0.2, f'串联组{group_id}',
                    ha='center', va='bottom', color='black', fontsize=7, fontweight='bold'
                )

        # 下方子图样式
        ax_bottom.set_xlim(-max_relative_end * 0.05, max_relative_end * 1.1)
        ax_bottom.set_ylim(0, y_pos_current + 1)
        ax_bottom.set_yticks(y_ticks)
        ax_bottom.set_yticklabels(y_tick_labels, fontsize=9)
        ax_bottom.set_xlabel(f'相对时间（分析阶段从全局时间 {analysis_start_offset} 开始）', fontsize=11)
        ax_bottom.set_title('下方：分析阶段（相对时间，以自身最早开始时间为0点）', fontsize=12, pad=10)
        ax_bottom.grid(True, axis='x', linestyle='--', alpha=0.7)

        # 图例
        legend_items = []
        for wp in range(min(5, self.num_workpieces)):
            legend_items.append(mpatches.Patch(color=base_colors[wp], label=f'气瓶 {wp}'))
        if self.num_workpieces > 5:
            legend_items.append(mpatches.Patch(color='white', label=f'... 共{self.num_workpieces}个气瓶'))
        if self.num_components > 0:
            wp_example = 0
            for comp in range(min(3, self.num_components)):
                legend_items.append(mpatches.Patch(
                    color=wp_comp_colors[(wp_example, comp)],
                    label=f'气瓶{wp_example}-组分{comp}'
                ))
        legend_items.append(mpatches.Patch(color='red', linestyle='--', label='阶段分隔线'))
        legend_items.append(mpatches.Patch(color='black', linestyle='--', label='分析串联组'))

        fig.legend(
            handles=legend_items, loc='lower center', ncol=6,
            bbox_to_anchor=(0.5, 0.02), fontsize=10
        )

        plt.tight_layout(rect=[0, 0.08, 1, 0.96])
        plt.show()

    def optimize(self):
        raise NotImplementedError("子类必须实现优化方法")


class GeneticAlgorithm(BaseSchedulingAlgorithm):
    """遗传算法"""

    def __init__(self,
                 instance: Dict,
                 population_size: int = 50,
                 max_iter: int = 100,
                 crossover_rate: float = 0.8,
                 mutation_rate: float = 0.1,
                 name: str = "遗传算法(GA)"):
        super().__init__(instance, max_iter, name)
        self.population_size = population_size
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.population = []

    def initialize_population(self):
        self.population = [self.initialize_solution() for _ in range(self.population_size)]

    def select_parents(self, fitness_values: List[float]) -> Tuple[Dict, Dict]:
        total_fitness = sum(fitness_values)
        probabilities = [f / total_fitness for f in fitness_values]
        parent1_idx = np.random.choice(self.population_size, p=probabilities)
        parent2_idx = np.random.choice(self.population_size, p=probabilities)
        while parent1_idx == parent2_idx:
            parent2_idx = np.random.choice(self.population_size, p=probabilities)
        return self.population[parent1_idx], self.population[parent2_idx]

    def crossover(self, parent1: Dict, parent2: Dict) -> Tuple[Dict, Dict]:
        if random.random() > self.crossover_rate:
            return parent1.copy(), parent2.copy()

        def order_crossover(order1, order2):
            size = len(order1)
            a, b = random.sample(range(size), 2)
            if a > b:
                a, b = b, a
            child1, child2 = [-1] * size, [-1] * size
            child1[a:b + 1] = order1[a:b + 1]
            child2[a:b + 1] = order2[a:b + 1]

            def fill_child(child, parent, start, end):
                ptr = (end + 1) % size
                for i in range(end + 1, end + 1 + size):
                    current = parent[i % size]
                    if current not in child:
                        child[ptr] = current
                        ptr = (ptr + 1) % size
                return child

            return fill_child(child1, order2, a, b), fill_child(child2, order1, a, b)

        # 交叉各阶段顺序
        child1_clean, child2_clean = order_crossover(parent1['clean_order'], parent2['clean_order'])
        child1_shake, child2_shake = order_crossover(parent1['shake_order'], parent2['shake_order'])
        child1_analysis, child2_analysis = order_crossover(parent1['analysis_order'], parent2['analysis_order'])
        child1_inflate, child2_inflate = order_crossover(parent1['inflation_order'], parent2['inflation_order'])

        # 交叉设备分配
        child1_clean_eq = parent1['clean_eq'].copy()
        child2_clean_eq = parent2['clean_eq'].copy()
        child1_shake_eq = parent1['shake_eq'].copy()
        child2_shake_eq = parent2['shake_eq'].copy()
        child1_inflate_eq = [row.copy() for row in parent1['inflation_eq']]
        child2_inflate_eq = [row.copy() for row in parent2['inflation_eq']]
        for wp in range(self.num_workpieces):
            for comp in range(self.num_components):
                if random.random() < 0.5:
                    child1_inflate_eq[wp][comp], child2_inflate_eq[wp][comp] = \
                        child2_inflate_eq[wp][comp], child1_inflate_eq[wp][comp]

        # 构建子染色体
        child1 = {
            'clean_order': child1_clean, 'clean_eq': child1_clean_eq,
            'inflation_order': child1_inflate, 'inflation_eq': child1_inflate_eq,
            'shake_order': child1_shake, 'shake_eq': child1_shake_eq,
            'analysis_order': child1_analysis,
            'component_groups': [g.copy() for g in parent1['component_groups']],
            'group_test_order': [g.copy() for g in parent1['group_test_order']],
            'analysis_eq': [g.copy() for g in parent1['analysis_eq']]
        }
        for i in range(len(child1['analysis_eq'])):
            child1['analysis_eq'][i] = [e.copy() for e in child1['analysis_eq'][i]]

        child2 = {
            'clean_order': child2_clean, 'clean_eq': child2_clean_eq,
            'inflation_order': child2_inflate, 'inflation_eq': child2_inflate_eq,
            'shake_order': child2_shake, 'shake_eq': child2_shake_eq,
            'analysis_order': child2_analysis,
            'component_groups': [g.copy() for g in parent2['component_groups']],
            'group_test_order': [g.copy() for g in parent2['group_test_order']],
            'analysis_eq': [g.copy() for g in parent2['analysis_eq']]
        }
        for i in range(len(child2['analysis_eq'])):
            child2['analysis_eq'][i] = [e.copy() for e in child2['analysis_eq'][i]]

        return child1, child2

    def mutate(self, chromosome: Dict) -> Dict:
        mutated = {
            'clean_order': chromosome['clean_order'].copy(),
            'clean_eq': chromosome['clean_eq'].copy(),
            'inflation_order': chromosome['inflation_order'].copy(),
            'inflation_eq': [row.copy() for row in chromosome['inflation_eq']],
            'shake_order': chromosome['shake_order'].copy(),
            'shake_eq': chromosome['shake_eq'].copy(),
            'analysis_order': chromosome['analysis_order'].copy(),
            'component_groups': [g.copy() for g in chromosome['component_groups']],
            'group_test_order': [g.copy() for g in chromosome['group_test_order']],
            'analysis_eq': [g.copy() for g in chromosome['analysis_eq']]
        }
        for i in range(len(mutated['analysis_eq'])):
            mutated['analysis_eq'][i] = [e.copy() for e in mutated['analysis_eq'][i]]

        # 顺序变异
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['clean_order'][idx1], mutated['clean_order'][idx2] = mutated['clean_order'][idx2], \
                mutated['clean_order'][idx1]
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['shake_order'][idx1], mutated['shake_order'][idx2] = mutated['shake_order'][idx2], \
                mutated['shake_order'][idx1]
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['analysis_order'][idx1], mutated['analysis_order'][idx2] = mutated['analysis_order'][idx2], \
                mutated['analysis_order'][idx1]

        # 充装顺序变异
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(len(mutated['inflation_order'])), 2)
            mutated['inflation_order'][idx1], mutated['inflation_order'][idx2] = \
                mutated['inflation_order'][idx2], mutated['inflation_order'][idx1]

        # 设备分配变异
        for i in range(self.num_workpieces):
            if random.random() < self.mutation_rate * 0.5:
                mutated['clean_eq'][i] = random.randint(0, self.num_clean_eq - 1)
            if random.random() < self.mutation_rate * 0.5:
                mutated['shake_eq'][i] = random.randint(0, self.num_shake_eq - 1)
            for comp in range(self.num_components):
                if random.random() < self.mutation_rate * 0.3:
                    mutated['inflation_eq'][i][comp] = random.randint(0, self.num_inflation_eq - 1)

        # 组分分组变异
        for i in range(self.num_workpieces):
            if random.random() < self.mutation_rate:
                comp_idx = random.randint(0, self.num_components - 1)
                current_groups = mutated['component_groups'][i]
                possible_groups = list(set(current_groups))
                if len(possible_groups) == 1:
                    new_group = 1 if possible_groups[0] == 0 else 0
                else:
                    new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
                current_groups[comp_idx] = new_group
                unique_groups = list(sorted(set(current_groups)))
                random.shuffle(unique_groups)
                mutated['group_test_order'][i] = unique_groups
                new_analysis_eq = []
                for group_id in unique_groups:
                    components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                    new_analysis_eq.append(
                        [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components_in_group])
                mutated['analysis_eq'][i] = new_analysis_eq

        return mutated

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()

        self.initialize_population()
        self.iteration_best_times = []
        self.best_time = float('inf')
        self.best_solution = None

        for generation in range(self.max_iter):
            try:
                completion_times = [self.time_of(chrom) for chrom in self.population]
                fitness_values = [1.0 / t for t in completion_times]
            except Exception as e:
                print(f"{self.name} 计算适应度时出错: {e}")
                self.initialize_population()
                completion_times = [self.time_of(chrom) for chrom in self.population]
                fitness_values = [1.0 / t for t in completion_times]

            current_best_idx = np.argmin(completion_times)
            current_best_time = completion_times[current_best_idx]
            current_best_solution = self.population[current_best_idx]

            self.iteration_best_times.append(current_best_time)

            if current_best_time < self.best_time:
                self.best_time = current_best_time
                self.best_solution = current_best_solution

            if generation % 10 == 0:
                print(f"{self.name} 第 {generation} 代: 最佳完成时间 = {current_best_time:.2f}")

            new_population = []
            elite_size = max(1, int(self.population_size * 0.1))
            elite_indices = np.argsort(completion_times)[:elite_size]
            for idx in elite_indices:
                new_population.append(self.population[idx])

            while len(new_population) < self.population_size:
                parent1, parent2 = self.select_parents(fitness_values)
                child1, child2 = self.crossover(parent1, parent2)
                child1 = self.mutate(child1)
                child2 = self.mutate(child2)
                new_population.append(child1)
                if len(new_population) < self.population_size:
                    new_population.append(child2)

            self.population = new_population

        self.execution_time = time.time() - start_time
        return self.best_solution, self.best_time


class ImprovedTabuSearch(BaseSchedulingAlgorithm):
    """改进禁忌搜索（含五种策略：原四种+优劣种群分离）"""

    def __init__(self,
                 instance: Dict,
                 population_size: int = 100,
                 tabu_size: int = 20,
                 neighborhood_size: int = 10,
                 max_iter: int = 100,
                 # 五种策略开关
                 use_elite_protection: bool = True,
                 dynamic_tabu_length: bool = True,
                 diverse_perturbation: bool = True,
                 history_heuristic: bool = True,
                 优劣种群分离: bool = True,  # 新增策略：优劣种群分离
                 name: str = "改进禁忌搜索(TS)"):
        super().__init__(instance, max_iter, name)
        self.population_size = population_size
        self.base_tabu_size = tabu_size
        self.tabu_size = tabu_size
        self.neighborhood_size = neighborhood_size
        self.tabu_list = []
        self.current_population = []

        # 策略开关
        self.use_elite_protection = use_elite_protection
        self.dynamic_tabu_length = dynamic_tabu_length
        self.diverse_perturbation = diverse_perturbation
        self.history_heuristic = history_heuristic
        self.优劣种群分离 = 优劣种群分离  # 新增策略开关

        self.history_best_times = []
        self.mutation_effectiveness = {}
        self.elite_pool = []
        self.elite_size = max(1, int(population_size * 0.1))

    def solution_hash(self, solution: Dict) -> int:
        """生成解的哈希值（补全分组与分析设备信息，避免禁忌误判）"""
        hash_tuple = (
                tuple(solution['clean_order']) + tuple(solution['clean_eq']) +
                tuple(solution['shake_order']) + tuple(solution['shake_eq']) +
                tuple(tuple(row) for row in solution['inflation_eq']) +
                tuple(solution['inflation_order']) +
                tuple(solution['analysis_order']) +
                # 关键：把分析分组与设备分配也纳入哈希
                tuple(tuple(g) for g in solution['component_groups']) +
                tuple(tuple(g) for g in solution['group_test_order']) +
                tuple(tuple(tuple(e) for e in work_g) for work_g in solution['analysis_eq'])
        )
        return hash(hash_tuple)

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()

        self.current_population = [self.initialize_solution() for _ in range(self.population_size)]
        self.best_time = float('inf')
        self.best_solution = None
        self.iteration_best_times = []
        self.tabu_list = []
        self.elite_pool = []

        self.mutation_effectiveness = {
            'clean_order': {'total': 0, 'count': 0},
            'clean_eq': {'total': 0, 'count': 0},
            'shake_order': {'total': 0, 'count': 0},
            'shake_eq': {'total': 0, 'count': 0},
            'inflation_order': {'total': 0, 'count': 0},
            'inflation_eq': {'total': 0, 'count': 0},
            'analysis_order': {'total': 0, 'count': 0},
            'group': {'total': 0, 'count': 0}
        }

        for iter in range(self.max_iter):
            # 策略1：动态禁忌长度
            if self.dynamic_tabu_length and iter > 0 and iter % 10 == 0:
                if len(self.history_best_times) >= 10:
                    recent_improve = self.history_best_times[-10] - self.history_best_times[-1]
                    if recent_improve < 0.05 * self.history_best_times[-10]:
                        self.tabu_size = min(int(self.base_tabu_size * 1.5), self.population_size * 2)
                    elif recent_improve > 0.2 * self.history_best_times[-10]:
                        self.tabu_size = max(int(self.base_tabu_size * 0.5), 5)
                    else:
                        self.tabu_size = self.base_tabu_size

            # 生成所有候选解
            all_candidates = []
            for solution in self.current_population:
                for _ in range(self.neighborhood_size):
                    mutation_types = [
                        'clean_order', 'clean_eq', 'shake_order', 'shake_eq',
                        'inflation_order', 'inflation_eq',
                        'analysis_order', 'group'
                    ]
                    mutation_type = random.choice(mutation_types)

                    new_solution = {
                        'clean_order': solution['clean_order'].copy(),
                        'clean_eq': solution['clean_eq'].copy(),
                        'inflation_order': solution['inflation_order'].copy(),
                        'inflation_eq': [row.copy() for row in solution['inflation_eq']],
                        'shake_order': solution['shake_order'].copy(),
                        'shake_eq': solution['shake_eq'].copy(),
                        'analysis_order': solution['analysis_order'].copy(),
                        'component_groups': [g.copy() for g in solution['component_groups']],
                        'group_test_order': [g.copy() for g in solution['group_test_order']],
                        'analysis_eq': [g.copy() for g in solution['analysis_eq']]
                    }
                    for i in range(len(new_solution['analysis_eq'])):
                        new_solution['analysis_eq'][i] = [e.copy() for e in new_solution['analysis_eq'][i]]

                    # 执行变异
                    if mutation_type == 'inflation_order':
                        if len(new_solution['inflation_order']) >= 2:
                            idx1, idx2 = random.sample(range(len(new_solution['inflation_order'])), 2)
                            new_solution['inflation_order'][idx1], new_solution['inflation_order'][idx2] = \
                                new_solution['inflation_order'][idx2], new_solution['inflation_order'][idx1]
                    elif mutation_type == 'inflation_eq':
                        wp = random.randint(0, self.num_workpieces - 1)
                        comp = random.randint(0, self.num_components - 1)
                        new_solution['inflation_eq'][wp][comp] = random.randint(0, self.num_inflation_eq - 1)
                    elif mutation_type == 'clean_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['clean_order'][idx1], new_solution['clean_order'][idx2] = \
                            new_solution['clean_order'][idx2], new_solution['clean_order'][idx1]
                    elif mutation_type == 'clean_eq':
                        idx = random.randint(0, self.num_workpieces - 1)
                        new_solution['clean_eq'][idx] = random.randint(0, self.num_clean_eq - 1)
                    elif mutation_type == 'shake_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['shake_order'][idx1], new_solution['shake_order'][idx2] = \
                            new_solution['shake_order'][idx2], new_solution['shake_order'][idx1]
                    elif mutation_type == 'shake_eq':
                        idx = random.randint(0, self.num_workpieces - 1)
                        new_solution['shake_eq'][idx] = random.randint(0, self.num_shake_eq - 1)
                    elif mutation_type == 'analysis_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['analysis_order'][idx1], new_solution['analysis_order'][idx2] = \
                            new_solution['analysis_order'][idx2], new_solution['analysis_order'][idx1]
                    elif mutation_type == 'group':
                        wp_idx = random.randint(0, self.num_workpieces - 1)
                        comp_idx = random.randint(0, self.num_components - 1)
                        current_groups = new_solution['component_groups'][wp_idx]
                        possible_groups = list(set(current_groups))
                        if len(possible_groups) == 1:
                            new_group = 1 if possible_groups[0] == 0 else 0
                        else:
                            new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
                        current_groups[comp_idx] = new_group
                        unique_groups = list(sorted(set(current_groups)))
                        random.shuffle(unique_groups)
                        new_solution['group_test_order'][wp_idx] = unique_groups
                        new_analysis_eq = []
                        for group_id in unique_groups:
                            components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                            new_analysis_eq.append([random.randint(0, self.num_analysis_eq_per_component - 1) for _ in
                                                    components_in_group])
                        new_solution['analysis_eq'][wp_idx] = new_analysis_eq

                    all_candidates.append((new_solution, mutation_type))

            # 处理候选解
            candidate_with_time = []
            seen_hashes = set()
            for candidate, mutation_type in all_candidates:
                candidate_hash = self.solution_hash(candidate)
                if candidate_hash not in seen_hashes:
                    seen_hashes.add(candidate_hash)
                    try:
                        t = self.time_of(candidate)
                        candidate_with_time.append((candidate, t, candidate_hash, mutation_type))
                    except Exception as e:
                        print(f"计算候选解时间出错: {e}")

            if not candidate_with_time:
                print(f"警告：第 {iter} 代未生成有效候选解，使用随机解替代")
                for _ in range(self.neighborhood_size):
                    new_sol = self.initialize_solution()
                    try:
                        t = self.time_of(new_sol)
                        candidate_with_time.append((new_sol, t, self.solution_hash(new_sol), "random"))
                    except Exception as e:
                        print(f"生成随机解出错: {e}")

            # 策略3：历史启发式排序
            if self.history_heuristic and len(self.history_best_times) > 0 and candidate_with_time:
                current_best = self.history_best_times[-1]
                scored_candidates = []
                for sol, t, h, mt in candidate_with_time:
                    improvement = max(0, current_best - t)
                    scored_candidates.append((sol, t, h, mt, improvement))
                scored_candidates.sort(key=lambda x: (x[1], -x[4]))
                candidate_with_time = [(x[0], x[1], x[2], x[3]) for x in scored_candidates]
            elif candidate_with_time:
                candidate_with_time.sort(key=lambda x: x[1])

            # 策略2：多样化扰动（更新变异效果）
            if candidate_with_time and self.diverse_perturbation:
                top_candidates = candidate_with_time[:int(len(candidate_with_time) * 0.2)]
                for sol, t, h, mt in top_candidates:
                    base_time = self.best_time if self.best_time != float('inf') else self.time_of(
                        self.current_population[0])
                    if t < base_time:
                        self.mutation_effectiveness[mt]['total'] += (base_time - t)
                        self.mutation_effectiveness[mt]['count'] += 1

            # 策略4：精英解保护
            if self.use_elite_protection and candidate_with_time:
                current_elites = candidate_with_time[:self.elite_size]
                self.elite_pool.extend(current_elites)
                unique_elites = {}
                for sol, t, h, mt in self.elite_pool:
                    if h not in unique_elites or t < unique_elites[h][1]:
                        unique_elites[h] = (sol, t, h, mt)
                self.elite_pool = list(unique_elites.values())
                self.elite_pool.sort(key=lambda x: x[1])
                self.elite_pool = self.elite_pool[:self.elite_size]

            # 构建新种群（含策略5：优劣种群分离）
            new_population = []

            # 加入精英解
            if self.use_elite_protection and self.elite_pool:
                new_population.extend([sol for sol, _, _, _ in self.elite_pool])

            # 选择非禁忌的优质解
            keep_count = self.population_size // 2  # 优质种群保留数量（种群一半）
            if candidate_with_time:
                for candidate, t, candidate_hash, mt in candidate_with_time:
                    if len(new_population) >= keep_count:
                        break
                    if candidate_hash not in self.tabu_list or t < self.best_time:
                        new_population.append(candidate)
                        self.tabu_list.append(candidate_hash)
                        if len(self.tabu_list) > self.tabu_size:
                            self.tabu_list.pop(0)

            # 策略5：优劣种群分离（劣质种群重新生成）
            if self.优劣种群分离:
                # 劣质种群数量 = 总种群 - 已保留的优质种群
                bad_count = self.population_size - len(new_population)
                # 重新生成劣质种群
                for _ in range(bad_count):
                    new_sol = self.initialize_solution()
                    new_population.append(new_sol)
            else:
                # 不启用时直接补充候选解
                while len(new_population) < self.population_size and candidate_with_time:
                    new_population.append(candidate_with_time[len(new_population)][0])

            self.current_population = new_population

            # 更新全局最优
            current_best_time = float('inf')
            current_best_solution = None
            for sol in self.current_population:
                try:
                    t = self.time_of(sol)
                    if t < current_best_time:
                        current_best_time = t
                        current_best_solution = sol
                except Exception as e:
                    print(f"计算种群解时间出错: {e}")

            if current_best_time < self.best_time:
                self.best_time = current_best_time
                self.best_solution = current_best_solution

            self.iteration_best_times.append(self.best_time)
            self.history_best_times.append(self.best_time)

            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.best_time:.2f}, 禁忌长度 = {self.tabu_size}")

        self.execution_time = time.time() - start_time
        return self.best_solution, self.best_time


class ParticleSwarmOptimization(BaseSchedulingAlgorithm):
    """粒子群优化"""

    def __init__(self,
                 instance: Dict,
                 swarm_size: int = 50,
                 max_iter: int = 100,
                 w: float = 0.7,
                 c1: float = 1.5,
                 c2: float = 1.5,
                 name: str = "粒子群优化(PSO)"):
        super().__init__(instance, max_iter, name)
        self.swarm_size = swarm_size
        self.w = w
        self.c1 = c1
        self.c2 = c2
        self.swarm = []
        self.pbest_solutions = []
        self.pbest_times = []
        self.gbest_solution = None
        self.gbest_time = float('inf')

    def initialize_swarm(self):
        self.swarm = [self.initialize_solution() for _ in range(self.swarm_size)]
        self.pbest_solutions = self.swarm.copy()
        self.pbest_times = [self.time_of(sol) for sol in self.swarm]
        self.gbest_time = min(self.pbest_times)
        self.gbest_solution = self.pbest_solutions[self.pbest_times.index(self.gbest_time)]

    def update_velocity(self, particle_idx):
        current_sol = self.swarm[particle_idx]
        pbest_sol = self.pbest_solutions[particle_idx]
        gbest_sol = self.gbest_solution

        mutation_type = random.choice([
            'clean_order', 'clean_eq', 'shake_order', 'shake_eq',
            'inflation_order', 'inflation_eq', 'analysis_order', 'group'
        ])

        new_sol = {
            'clean_order': current_sol['clean_order'].copy(),
            'clean_eq': current_sol['clean_eq'].copy(),
            'inflation_order': current_sol['inflation_order'].copy(),
            'inflation_eq': [row.copy() for row in current_sol['inflation_eq']],
            'shake_order': current_sol['shake_order'].copy(),
            'shake_eq': current_sol['shake_eq'].copy(),
            'analysis_order': current_sol['analysis_order'].copy(),
            'component_groups': [g.copy() for g in current_sol['component_groups']],
            'group_test_order': [g.copy() for g in current_sol['group_test_order']],
            'analysis_eq': [g.copy() for g in current_sol['analysis_eq']]
        }
        for i in range(len(new_sol['analysis_eq'])):
            new_sol['analysis_eq'][i] = [e.copy() for e in new_sol['analysis_eq'][i]]

        if random.random() < self.c1:
            if mutation_type == 'inflation_order':
                idx = random.randint(0, len(new_sol['inflation_order']) - 1)
                new_sol['inflation_order'][idx] = pbest_sol['inflation_order'][idx]
            elif mutation_type == 'inflation_eq':
                wp = random.randint(0, self.num_workpieces - 1)
                comp = random.randint(0, self.num_components - 1)
                new_sol['inflation_eq'][wp][comp] = pbest_sol['inflation_eq'][wp][comp]

        if random.random() < self.c2:
            if mutation_type == 'inflation_order':
                idx = random.randint(0, len(new_sol['inflation_order']) - 1)
                new_sol['inflation_order'][idx] = gbest_sol['inflation_order'][idx]
            elif mutation_type == 'inflation_eq':
                wp = random.randint(0, self.num_workpieces - 1)
                comp = random.randint(0, self.num_components - 1)
                new_sol['inflation_eq'][wp][comp] = gbest_sol['inflation_eq'][wp][comp]

        if random.random() < self.w:
            if mutation_type == 'inflation_order' and len(new_sol['inflation_order']) >= 2:
                idx1, idx2 = random.sample(range(len(new_sol['inflation_order'])), 2)
                new_sol['inflation_order'][idx1], new_sol['inflation_order'][idx2] = \
                    new_sol['inflation_order'][idx2], new_sol['inflation_order'][idx1]
            elif mutation_type == 'inflation_eq':
                wp = random.randint(0, self.num_workpieces - 1)
                comp = random.randint(0, self.num_components - 1)
                new_sol['inflation_eq'][wp][comp] = random.randint(0, self.num_inflation_eq - 1)

        return new_sol

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()
        self.initialize_swarm()
        self.iteration_best_times = []

        for iter in range(self.max_iter):
            for i in range(self.swarm_size):
                new_sol = self.update_velocity(i)
                try:
                    new_time = self.time_of(new_sol)
                except Exception as e:
                    print(f"PSO计算新解时间出错: {e}")
                    continue

                if new_time < self.pbest_times[i]:
                    self.pbest_solutions[i] = new_sol
                    self.pbest_times[i] = new_time
                    if new_time < self.gbest_time:
                        self.gbest_time = new_time
                        self.gbest_solution = new_sol

                self.swarm[i] = new_sol

            self.iteration_best_times.append(self.gbest_time)
            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.gbest_time:.2f}")

        self.best_solution = self.gbest_solution
        self.best_time = self.gbest_time
        self.execution_time = time.time() - start_time
        return self.best_solution, self.best_time


class SimulatedAnnealing(BaseSchedulingAlgorithm):
    """模拟退火"""

    def __init__(self,
                 instance: Dict,
                 init_temp: float = 100.0,
                 cool_rate: float = 0.95,
                 max_iter: int = 100,
                 name: str = "模拟退火(SA)"):
        super().__init__(instance, max_iter, name)
        self.init_temp = init_temp
        self.cool_rate = cool_rate
        self.current_temp = init_temp
        self.current_solution = None
        self.current_time = float('inf')

    def generate_neighbor(self, solution: Dict) -> Dict:
        """邻域生成：覆盖四阶段与分析分组/设备的关键变异"""
        new_sol = {
            'clean_order': solution['clean_order'].copy(),
            'clean_eq': solution['clean_eq'].copy(),
            'inflation_order': solution['inflation_order'].copy(),
            'inflation_eq': [row.copy() for row in solution['inflation_eq']],
            'shake_order': solution['shake_order'].copy(),
            'shake_eq': solution['shake_eq'].copy(),
            'analysis_order': solution['analysis_order'].copy(),
            'component_groups': [g.copy() for g in solution['component_groups']],
            'group_test_order': [g.copy() for g in solution['group_test_order']],
            'analysis_eq': [[e.copy() for e in work_g] for work_g in solution['analysis_eq']]
        }

        mutation_type = random.choice([
            'clean_order', 'clean_eq',
            'shake_order', 'shake_eq',
            'inflation_order', 'inflation_eq',
            'analysis_order', 'group', 'analysis_eq'
        ])

        if mutation_type == 'inflation_order' and len(new_sol['inflation_order']) >= 2:
            # 交换两条充装工序（保持每瓶内部 N2 最后约束——通过拒绝非法交换实现）
            i, j = sorted(random.sample(range(len(new_sol['inflation_order'])), 2))
            (wp_i, comp_i), (wp_j, comp_j) = new_sol['inflation_order'][i], new_sol['inflation_order'][j]
            bottom = self.num_components - 1

            def ok(seq, idx_from, idx_to):
                wp, comp = seq[idx_from]
                # 若尝试把底气移动到该瓶其他组分之前，则拒绝
                if comp == bottom:
                    # 若目标位置之前仍存在该瓶其他组分，则非法
                    prior = [k for k, (w, c) in enumerate(seq) if w == wp and c != bottom]
                    if prior and min(prior) < idx_to:
                        return False
                return True

            if ok(new_sol['inflation_order'], j, i) and ok(new_sol['inflation_order'], i, j):
                new_sol['inflation_order'][i], new_sol['inflation_order'][j] = new_sol['inflation_order'][j], \
                new_sol['inflation_order'][i]

        elif mutation_type == 'inflation_eq':
            wp = random.randint(0, self.num_workpieces - 1)
            comp = random.randint(0, self.num_components - 1)
            new_sol['inflation_eq'][wp][comp] = random.randint(0, self.num_inflation_eq - 1)

        elif mutation_type == 'clean_order' and self.num_workpieces >= 2:
            i, j = random.sample(range(self.num_workpieces), 2)
            new_sol['clean_order'][i], new_sol['clean_order'][j] = new_sol['clean_order'][j], new_sol['clean_order'][i]

        elif mutation_type == 'clean_eq':
            i = random.randint(0, self.num_workpieces - 1)
            new_sol['clean_eq'][i] = random.randint(0, self.num_clean_eq - 1)

        elif mutation_type == 'shake_order' and self.num_workpieces >= 2:
            i, j = random.sample(range(self.num_workpieces), 2)
            new_sol['shake_order'][i], new_sol['shake_order'][j] = new_sol['shake_order'][j], new_sol['shake_order'][i]

        elif mutation_type == 'shake_eq':
            i = random.randint(0, self.num_workpieces - 1)
            new_sol['shake_eq'][i] = random.randint(0, self.num_shake_eq - 1)

        elif mutation_type == 'analysis_order' and self.num_workpieces >= 2:
            i, j = random.sample(range(self.num_workpieces), 2)
            new_sol['analysis_order'][i], new_sol['analysis_order'][j] = new_sol['analysis_order'][j], \
            new_sol['analysis_order'][i]

        elif mutation_type == 'group':
            # 随机选择一个工件，调整其分组与对应设备
            wp = random.randint(0, self.num_workpieces - 1)
            groups = new_sol['component_groups'][wp]
            if self.num_components >= 2:
                comp_idx = random.randint(0, self.num_components - 1)
                # 在已有组中换组；若只有一组则新增/切换到另一组标号
                possible = sorted(set(groups))
                if len(possible) == 1:
                    new_group = 1 if possible[0] == 0 else 0
                else:
                    new_group = random.choice([g for g in possible if g != groups[comp_idx]])
                groups[comp_idx] = new_group
            # 重建该工件的组顺序与组内设备选择
            unique_groups = list(sorted(set(groups)))
            random.shuffle(unique_groups)
            new_sol['group_test_order'][wp] = unique_groups
            new_analysis_eq = []
            for gid in unique_groups:
                comps_in_g = [j for j, g in enumerate(groups) if g == gid]
                new_analysis_eq.append([random.randint(0, self.num_analysis_eq_per_component - 1)
                                        for _ in comps_in_g])
            new_sol['analysis_eq'][wp] = new_analysis_eq

        elif mutation_type == 'analysis_eq':
            # 随机改变某工件某组的设备指派
            wp = random.randint(0, self.num_workpieces - 1)
            if new_sol['analysis_eq'][wp]:
                gidx = random.randint(0, len(new_sol['analysis_eq'][wp]) - 1)
                if new_sol['analysis_eq'][wp][gidx]:
                    cidx = random.randint(0, len(new_sol['analysis_eq'][wp][gidx]) - 1)
                    new_sol['analysis_eq'][wp][gidx][cidx] = random.randint(0, self.num_analysis_eq_per_component - 1)

        return new_sol

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()
        self.current_solution = self.initialize_solution()
        self.current_time = self.time_of(self.current_solution)
        self.best_solution = self.current_solution.copy()
        self.best_time = self.current_time
        self.iteration_best_times = [self.best_time]

        for iter in range(self.max_iter):
            neighbor_sol = self.generate_neighbor(self.current_solution)
            try:
                neighbor_time = self.time_of(neighbor_sol)
            except Exception as e:
                print(f"SA计算邻域解时间出错: {e}")
                continue

            delta = neighbor_time - self.current_time

            if delta < 0 or random.random() < np.exp(-delta / self.current_temp):
                self.current_solution = neighbor_sol
                self.current_time = neighbor_time

                if self.current_time < self.best_time:
                    self.best_time = self.current_time
                    self.best_solution = self.current_solution.copy()

            self.current_temp *= self.cool_rate
            self.iteration_best_times.append(self.best_time)

            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.best_time:.2f}, 温度 = {self.current_temp:.2f}")

        self.execution_time = time.time() - start_time
        return self.best_solution, self.best_time


def plot_convergence_comparison(algorithms: List[BaseSchedulingAlgorithm]):
    """绘制算法收敛曲线对比"""
    plt.figure(figsize=(12, 8))
    styles = [
        {'color': 'blue', 'linestyle': '-', 'marker': 'o', 'label': algorithms[0].name},
        {'color': 'green', 'linestyle': '--', 'marker': 's', 'label': algorithms[1].name},
        {'color': 'red', 'linestyle': '-.', 'marker': '^', 'label': algorithms[2].name},
        {'color': 'purple', 'linestyle': ':', 'marker': 'd', 'label': algorithms[3].name}
    ]

    for i, algorithm in enumerate(algorithms):
        if i < len(styles):
            style = styles[i]
            plt.plot(range(1, len(algorithm.iteration_best_times) + 1),
                     algorithm.iteration_best_times,
                     color=style['color'], linestyle=style['linestyle'],
                     marker=style['marker'], markersize=4, linewidth=2, label=style['label'])

    plt.xlabel('迭代次数')
    plt.ylabel('最大完成时间')
    plt.title('不同算法收敛曲线对比')
    plt.grid(True, linestyle='--', alpha=0.7)
    plt.legend()
    plt.tight_layout()
    plt.show()


def select_instance():
    """选择算例"""
    print("===== 算例选择 =====")
    instance_files = GasSchedulingInstanceGenerator.list_instances()

    if not instance_files:
        print("未找到算例，请先生成算例！")
        exit(1)

    for i, file_path in enumerate(instance_files, 1):
        try:
            with open(file_path, 'r') as f:
                data = json.load(f)
                wp = data['parameters'].get('num_workpieces', '未知')
                comp = data['parameters'].get('num_components', '未知')
                print(f"{i}. {file_path} (工件数: {wp}, 组分数: {comp})")
        except:
            print(f"{i}. {file_path} (格式可能不正确)")

    while True:
        try:
            choice = int(input(f"请选择算例 (1-{len(instance_files)}): ")) - 1
            if 0 <= choice < len(instance_files):
                selected_file = instance_files[choice]
                print(f"已选择算例: {selected_file}")
                return selected_file, GasSchedulingInstanceGenerator.load_instance(selected_file)
        except ValueError:
            print("请输入有效数字")


def main():
    # 设定随机种子，保证复现实验
    set_seed(42)
    """主函数：四种算法对比"""
    # 选择算例
    instance_path, instance = select_instance()

    # 初始化四种算法（含改进禁忌搜索）
    algorithms = [
        GeneticAlgorithm(instance, max_iter=100, name="遗传算法(GA)"),
        ImprovedTabuSearch(instance, max_iter=100, name="改进禁忌搜索(TS)"),
        ParticleSwarmOptimization(instance, max_iter=100, name="粒子群优化(PSO)"),
        SimulatedAnnealing(instance, max_iter=100, name="模拟退火(SA)")
    ]

    # 运行算法
    for algo in algorithms:
        print(f"\n===== 开始运行 {algo.name} =====")
        best_solution, best_time = algo.optimize()
        print(f"{algo.name} 最佳完成时间: {best_time:.2f}")
        print(f"{algo.name} 执行时间: {algo.execution_time:.2f}秒")
        algo.plot_gantt_chart(title_suffix=f"(最佳时间: {best_time:.2f})")

    # 绘制收敛曲线对比
    plot_convergence_comparison(algorithms)

    # 输出结果汇总
    print("\n===== 算法对比结果汇总 =====")
    for algo in algorithms:
        print(f"{algo.name}: 最佳完成时间 = {algo.best_time:.2f}")


if __name__ == "__main__":
    main()